import java.util.Scanner;

public class demo01 {
    public static void main(String[] args) {
        //星际密码
        int[] nums=new int[10001];
        nums[1]=1;
        nums[2]=2;
        for (int i = 3; i < 10001; i++) {
            nums[i]=nums[i-1]+nums[i-2];
            nums[i]=nums[i]%10000;
        }
        Scanner sc=new Scanner(System.in);
        while (sc.hasNext()){
            StringBuilder sb=new StringBuilder();
            int n=sc.nextInt();
            for (int i = 0; i < n; i++) {
                int x=sc.nextInt();
                sb.append(String.format("%04d",nums[x]));
            }
            System.out.println(sb);
        }
    }
}
